{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Alloys"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxNumberOfAlloys"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大合金数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>假设你是一家合金制造公司的老板，你的公司使用多种金属来制造合金。现在共有 <code>n</code> 种不同类型的金属可以使用，并且你可以使用 <code>k</code> 台机器来制造合金。每台机器都需要特定数量的每种金属来创建合金。</p>\n",
    "\n",
    "<p>对于第 <code>i</code> 台机器而言，创建合金需要 <code>composition[i][j]</code> 份 <code>j</code> 类型金属。最初，你拥有 <code>stock[i]</code> 份 <code>i</code> 类型金属，而每购入一份 <code>i</code> 类型金属需要花费 <code>cost[i]</code> 的金钱。</p>\n",
    "\n",
    "<p>给你整数 <code>n</code>、<code>k</code>、<code>budget</code>，下标从 <strong>1</strong> 开始的二维数组 <code>composition</code>，两个下标从 <strong>1</strong> 开始的数组 <code>stock</code> 和 <code>cost</code>，请你在预算不超过 <code>budget</code> 金钱的前提下，<strong>最大化</strong> 公司制造合金的数量。</p>\n",
    "\n",
    "<p><strong>所有合金都需要由同一台机器制造。</strong></p>\n",
    "\n",
    "<p>返回公司可以制造的最大合金数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,0], cost = [1,2,3]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>最优的方法是使用第 1 台机器来制造合金。\n",
    "要想制造 2 份合金，我们需要购买：\n",
    "- 2 份第 1 类金属。\n",
    "- 2 份第 2 类金属。\n",
    "- 2 份第 3 类金属。\n",
    "总共需要 2 * 1 + 2 * 2 + 2 * 3 = 12 的金钱，小于等于预算 15 。\n",
    "注意，我们最开始时候没有任何一类金属，所以必须买齐所有需要的金属。\n",
    "可以证明在示例条件下最多可以制造 2 份合金。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,100], cost = [1,2,3]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>最优的方法是使用第 2 台机器来制造合金。 \n",
    "要想制造 5 份合金，我们需要购买： \n",
    "- 5 份第 1 类金属。\n",
    "- 5 份第 2 类金属。 \n",
    "- 0 份第 3 类金属。 \n",
    "总共需要 5 * 1 + 5 * 2 + 0 * 3 = 15 的金钱，小于等于预算 15 。 \n",
    "可以证明在示例条件下最多可以制造 5 份合金。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, k = 3, budget = 10, composition = [[2,1],[1,2],[1,1]], stock = [1,1], cost = [5,5]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>最优的方法是使用第 3 台机器来制造合金。\n",
    "要想制造 2 份合金，我们需要购买：\n",
    "- 1 份第 1 类金属。\n",
    "- 1 份第 2 类金属。\n",
    "总共需要 1 * 5 + 1 * 5 = 10 的金钱，小于等于预算 10 。\n",
    "可以证明在示例条件下最多可以制造 2 份合金。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n, k &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= budget &lt;= 10<sup>8</sup></code></li>\n",
    "\t<li><code>composition.length == k</code></li>\n",
    "\t<li><code>composition[i].length == n</code></li>\n",
    "\t<li><code>1 &lt;= composition[i][j] &lt;= 100</code></li>\n",
    "\t<li><code>stock.length == cost.length == n</code></li>\n",
    "\t<li><code>0 &lt;= stock[i] &lt;= 10<sup>8</sup></code></li>\n",
    "\t<li><code>1 &lt;= cost[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-alloys](https://leetcode.cn/problems/maximum-number-of-alloys/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-alloys](https://leetcode.cn/problems/maximum-number-of-alloys/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n2\\n15\\n[[1,1,1],[1,1,10]]\\n[0,0,0]\\n[1,2,3]', '3\\n2\\n15\\n[[1,1,1],[1,1,10]]\\n[0,0,100]\\n[1,2,3]', '2\\n3\\n10\\n[[2,1],[1,2],[1,1]]\\n[1,1]\\n[5,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = min(stock) + budget\n",
    "        for com in composition:\n",
    "            def check(num: int) -> int:\n",
    "                money = 0\n",
    "                for s, base, c in zip(stock, com, cost):\n",
    "                    if s < base * num:\n",
    "                        money += (base * num - s) * c\n",
    "                        if money > budget:\n",
    "                            return False\n",
    "                return True\n",
    "\n",
    "            left, right = 0, mx + 1\n",
    "            while left + 1 < right:  # 开区间写法\n",
    "                mid = (left + right) // 2\n",
    "                if check(mid):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "            ans = max(ans, left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        def check(target):\n",
    "            for compo in composition:\n",
    "                t = 0\n",
    "                for a, b in zip(compo, cost):\n",
    "                    t += a * b\n",
    "                t *= target\n",
    "                for i, st in enumerate(stock):\n",
    "                    t -= min(target * compo[i], st) * cost[i]\n",
    "                if t <= budget:\n",
    "                    return True\n",
    "            return False\n",
    "        l, r = 0, 10**9\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if(check(mid)):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(\n",
    "        self,\n",
    "        n: int,\n",
    "        k: int,\n",
    "        budget: int,\n",
    "        composition: List[List[int]],\n",
    "        stock: List[int],\n",
    "        cost: List[int],\n",
    "    ) -> int:\n",
    "        def check(num):\n",
    "            money = 0\n",
    "            for s, base, c in zip(stock, com, cost):\n",
    "                if s < base * num:  # 需要额外购买\n",
    "                    money += (base * num - s) * c\n",
    "                    # if money > budget:\n",
    "                        # return False\n",
    "            return money <= budget\n",
    "            # return True\n",
    "\n",
    "        ans = 0\n",
    "        for com in composition:\n",
    "            l, r = 0, 2 * 10**8\n",
    "            while l < r:\n",
    "                mid = (l + r + 1) >> 1\n",
    "                if check(mid):\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            ans = max(ans, l)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        l = 0\n",
    "        r = max(stock) + budget + 1\n",
    "        def check(m):\n",
    "            for i in range(k):\n",
    "                cnt = 0\n",
    "                for j in range(n):\n",
    "                    need = composition[i][j] * m - stock[j]\n",
    "                    if need > 0:\n",
    "                        cnt += need * cost[j]\n",
    "                if cnt <= budget:\n",
    "                    return 1\n",
    "            return 0\n",
    "                \n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l - 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        def helper(compositions):\n",
    "            left=0\n",
    "            right=10**8+max(stock)\n",
    "            while left <right:\n",
    "                middle=(left+right+1)//2\n",
    "                c=sum([  (compositions[x]*middle-stock[x] if compositions[x]*middle-stock[x]>0 else 0)*cost[x] for x in range(n)])\n",
    "                if c>budget:\n",
    "                    right= middle-1\n",
    "                else:\n",
    "                    left=middle\n",
    "\n",
    "            return left\n",
    "        return max([helper(x) for x in composition])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        #二分\n",
    "        ans = 0\n",
    "        mx = budget+min(stock)\n",
    "        for com in composition:\n",
    "            def check(num):\n",
    "                money = 0\n",
    "                for s,per,c in zip(stock,com,cost):\n",
    "                    if s<per*num:\n",
    "                        money += (per*num-s)*c\n",
    "                        if money>budget:\n",
    "                            return False\n",
    "                return True\n",
    "            left = 0\n",
    "            right = mx+1\n",
    "            while left+1<right:\n",
    "                mid = (left+right)//2\n",
    "                if check(mid):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "            ans = max(ans,left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        # 给定一个区间，不断地二分答案，找到最大的满足预算的可制造合金数\n",
    "        ans = 0\n",
    "        # 定义上界，因为制造合金数与 budget 和 stock[i] 有关，因此上界最多可制造 10^8 + 10^8 个合金\n",
    "        mx = int(2e8)\n",
    "        for com in composition:\n",
    "            def check(num: int) -> bool:\n",
    "                money = 0\n",
    "                for s, base, c in zip(stock, com, cost):\n",
    "                    # 库存不够，需要额外购买\n",
    "                    if s < base * num:\n",
    "                        # 需要额外花费\n",
    "                        money += (base * num - s) * c\n",
    "                        # 总花费已经超出预算，那么这个二分值不合法，缩小右端点\n",
    "                        if money > budget: return False\n",
    "                # 总花费符合预算，扩大左端点\n",
    "                return True\n",
    "            # 二分模板，开区间写法\n",
    "            left, right = 0, mx + 1\n",
    "            # 不断地二分，找到最大合法值\n",
    "            while left + 1 < right:\n",
    "                mid = (left + right) // 2\n",
    "                if check(mid):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "            ans = max(ans, left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = min(stock) + budget\n",
    "        for com in composition:\n",
    "            def check(num: int) -> int:\n",
    "                money = 0\n",
    "                for s, base, c in zip(stock, com, cost):\n",
    "                    if s < base * num:\n",
    "                        money += (base * num - s) * c\n",
    "                        if money > budget:\n",
    "                            return False\n",
    "                return True\n",
    "            left,right = 0, mx+1\n",
    "            while left + 1 < right:  # 开区间写法\n",
    "                mid = (left + right) // 2\n",
    "                if check(mid):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "            ans = max(ans, left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        \n",
    "        def check(n,comp,budget=budget):\n",
    "            for j, c in enumerate(comp):\n",
    "                budget -= (max(n * c - stock[j],0) * cost[j])\n",
    "            # print(n,budget)\n",
    "            return budget >= 0\n",
    "\n",
    "        max_num = 0\n",
    "        for comp in composition:\n",
    "            min_comp = min(comp)\n",
    "            \n",
    "            upper_bound = budget// (min(cost) * min_comp) + max(stock) // min_comp + 1\n",
    "            # print(upper_bound)\n",
    "            l,r = 0, upper_bound\n",
    "            while l < r:\n",
    "                mid = (l+r+1) //2 \n",
    "                if check(mid,comp):\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            # print(l,r)\n",
    "            max_num = max(max_num,l)\n",
    "        return max_num\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i,req in enumerate(composition):\n",
    "            l,h = 0, budget + max(stock)\n",
    "            while l < h:\n",
    "                m = (l+h+1)//2\n",
    "                tmp = sum([c*max(0,r*m-s) for s,c,r in zip(stock,cost,req)])\n",
    "                \n",
    "                if tmp <= budget:\n",
    "                    l = m \n",
    "                else:\n",
    "                    h = m-1\n",
    "            res = max(res,h)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        # 二分查找函数\n",
    "        return max(bisect_left(range(1000000000),\n",
    "                               True,\n",
    "                               key=lambda x: sum(max(0, x * m - s) * c\n",
    "                                                 for m, s, c in zip(mc, stock, cost)) > budget)\n",
    "                   for mc in composition) - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        def check(x, comp, stock):\n",
    "            x_cost = 0\n",
    "            for i in range(n):\n",
    "                x_cost += max(comp[i]*x - stock[i], 0)*cost[i]\n",
    "                if(x_cost > budget):\n",
    "                    return False\n",
    "            return True\n",
    "        result = 0\n",
    "        for comp in composition:\n",
    "            left, right = 0, budget + max(stock)\n",
    "            while(left <= right):\n",
    "                mid = (left + right) // 2\n",
    "                if(check(mid, comp, stock)):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            result = max(right,result)\n",
    "        return result\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        return max(bisect_left(range(1000000000),\n",
    "                               True,\n",
    "                               key=lambda x: sum(max(0, x * m - s) * c\n",
    "                                                 for m, s, c in zip(mc, stock, cost)) > budget)\n",
    "                   for mc in composition) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        ans=0\n",
    "        for com in composition:\n",
    "            def check(num:int)->bool:\n",
    "                money=0\n",
    "                for s,base,c in zip(stock,com,cost):\n",
    "                    if s<base*num:\n",
    "                        money+=(base*num-s)*c\n",
    "                        if money>budget:\n",
    "                            return False\n",
    "                return True\n",
    "            left,right=0,min(stock)+budget\n",
    "            while left<=right:\n",
    "                mid=(left+right)//2\n",
    "                if check(mid):\n",
    "                    left=mid+1\n",
    "                else:\n",
    "                    right=mid-1\n",
    "            ans=max(ans,left-1)#要么写ans=max(ans,right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        ans=0\n",
    "        for com in composition:\n",
    "            def check(num:int)->bool:\n",
    "                money=0\n",
    "                for s,base,c in zip(stock,com,cost):\n",
    "                    if s<base*num:\n",
    "                        money+=(base*num-s)*c\n",
    "                        if money>budget:\n",
    "                            return False\n",
    "                return True\n",
    "            left,right=0,min(stock)+budget\n",
    "            while left<=right:\n",
    "                mid=(left+right)//2\n",
    "                if check(mid):\n",
    "                    left=mid+1\n",
    "                else:\n",
    "                    right=mid-1\n",
    "            ans=max(ans,left-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        # 二分答案\n",
    "        ans = 0\n",
    "        mx = min(stock) + budget\n",
    "        for com in composition:\n",
    "            def check(num: int) -> int:\n",
    "                money = 0\n",
    "                for s, base, c in zip(stock, com, cost):\n",
    "                    if s < base * num:\n",
    "                        money += (base * num - s) * c\n",
    "                        if money > budget:\n",
    "                            return False\n",
    "                return True\n",
    "\n",
    "            left, right = 0, mx + 1\n",
    "            while left + 1 < right:  # 开区间写法\n",
    "                mid = (left + right) // 2\n",
    "                if check(mid):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "            ans = max(ans, left)\n",
    "        return ans\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        res = 0\n",
    "        mx = min(stock) + budget\n",
    "        def f(num, item):\n",
    "            total = 0\n",
    "            for x, y, z in zip(stock, item, cost):\n",
    "                if x < y * num:\n",
    "                    total += (y * num - x) * z\n",
    "                    if total > budget:\n",
    "                        return False\n",
    "            return True\n",
    "        for item in composition:\n",
    "            l, r = 0, mx + 1\n",
    "            while l + 1 < r:\n",
    "                m = (l + r) // 2\n",
    "                if f(m, item):\n",
    "                    l = m\n",
    "                else:\n",
    "                    r = m\n",
    "            res = max(res, l)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = min(stock) + budget\n",
    "        for com in composition:\n",
    "            def check(num: int) -> int:\n",
    "                money = 0\n",
    "                for s, base, c in zip(stock, com, cost):\n",
    "                    if s < base * num:\n",
    "                        money += (base * num - s) * c\n",
    "                        if money > budget:\n",
    "                            return False\n",
    "                return True\n",
    "\n",
    "            left, right = 0, mx + 1\n",
    "            while left + 1 < right:  # 开区间写法\n",
    "                mid = (left + right) // 2\n",
    "                if check(mid):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "            ans = max(ans, left)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        return max(bisect_left(range(min(stock) + budget//min(cost) + 1), True, key=lambda x: sum(max(0, x * m - s) * c for m, s, c in zip(mc, stock, cost)) > budget)  for mc in composition) - 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(\n",
    "        self,\n",
    "        n: int,\n",
    "        k: int,\n",
    "        budget: int,\n",
    "        composition: List[List[int]],\n",
    "        stock: List[int],\n",
    "        cost: List[int],\n",
    "    ) -> int:\n",
    "        def check(num):\n",
    "            money = 0\n",
    "            for s, base, c in zip(stock, com, cost):\n",
    "                if s < base * num:  # 需要额外购买\n",
    "                    money += (base * num - s) * c\n",
    "                    # if money > budget:\n",
    "                        # return False\n",
    "            return money <= budget\n",
    "            # return True\n",
    "\n",
    "        ans = 0\n",
    "        for com in composition:\n",
    "            l, r = 0, 2 * 10**8\n",
    "            while l < r:\n",
    "                mid = (l + r + 1) >> 1\n",
    "                if check(mid):\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            ans = max(ans, l)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "\n",
    "        left,right = 0, min(stock)+budget\n",
    "        while left <= right:\n",
    "            mid = left + (right-left)//2\n",
    "            flag = 0\n",
    "            for machine in composition:\n",
    "                need = 0\n",
    "                for i in range(n):\n",
    "                    if mid*machine[i] - stock[i] <= 0:continue\n",
    "                    need += (mid*machine[i]-stock[i])*cost[i]\n",
    "                if need <= budget:flag = 1\n",
    "                \n",
    "            if flag:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        # 确定总共制造出多少份合金，来判断是否能造出来\n",
    "        mx=min(stock)+budget\n",
    "        ans=0\n",
    "        for com in composition:\n",
    "            def check(num:int,budget:int) -> bool:\n",
    "                for s,base,c in zip(stock,com,cost):\n",
    "                    if s<base*num: # 说明为了达到能生产num个合金，必须要补充材料了\n",
    "                        budget-=(base*num-s)*c\n",
    "                        if budget<0: return False\n",
    "                return True      \n",
    "            # left=0\n",
    "            # right=mx+1 # 二分，设置一个开区间\n",
    "            # # 开区间二分的模版\n",
    "            # while left+1<right: # 始终确保区间内有一个元素\n",
    "            #     mid=(left+right)//2\n",
    "            #     if check(mid,budget):\n",
    "            #         left=mid # 只需讨论mid+1到mx之间的数，所以开区间是(mid,mx+1)\n",
    "            #     else:\n",
    "            #         right=mid\n",
    "            # ans=max(ans,left) # 最终二分终点一定是left+1=right，而这是个开区间，因此right一定不满足要求，所以满足要求的最大值一定是right-1=left\n",
    "\n",
    "            # left=0\n",
    "            # right=mx # 二分，设置一个闭区间\n",
    "            # while left<=right:\n",
    "            #     mid=(left+right)//2\n",
    "            #     if check(mid,budget):\n",
    "            #         left=mid+1\n",
    "            #     else:\n",
    "            #         right=mid-1\n",
    "            # ans=max(ans,right) # 二分终点一定是left-1=right\n",
    "\n",
    "            left=0\n",
    "            right=mx+1 # 二分，设置一个左闭右开区间\n",
    "            while left<right:\n",
    "                mid=(left+right)//2\n",
    "                if check(mid,budget):\n",
    "                    left=mid+1\n",
    "                else:\n",
    "                    right=mid\n",
    "            \n",
    "            ans=max(ans,right-1) # 二分终点是left=right\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        def check(mid: int, x: int) -> bool:\n",
    "            money = 0\n",
    "            com = composition[x]\n",
    "            for i in range(n):\n",
    "                ca = com[i] * mid - stock[i]\n",
    "                if ca>0: money+= (ca * cost[i])\n",
    "                if money>budget: return False\n",
    "            return True\n",
    "\n",
    "        mx = 0\n",
    "        for i in range(1,k+1):\n",
    "            l,r=0,min(stock) + budget\n",
    "            while l < r:\n",
    "                mid = l+r+1 >> 1\n",
    "                if check(mid,i-1): l = mid\n",
    "                else: r = mid - 1\n",
    "                # print(l,r)\n",
    "            if l > mx:\n",
    "                mx = l\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        return max(bisect.bisect_left(range(1000000000),\n",
    "                               True,\n",
    "                               key=lambda x: sum(max(0, x * m - s) * c\n",
    "                                                 for m, s, c in zip(mc, stock, cost)) > budget)\n",
    "                   for mc in composition) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        stocknum = len(stock)\n",
    "        ans = 0\n",
    "        for i, machine in enumerate(composition):\n",
    "            left = 0\n",
    "            right = 10**9+1\n",
    "            while left <= right:\n",
    "                mid = left + ((right-left)>>1)\n",
    "                sumcost = sum(cost[j] * max(0, mid*machine[j]-stock[j]) for j in range(stocknum))\n",
    "                # print(left, right ,mid)\n",
    "                if sumcost <= budget:\n",
    "                    if sum(cost[j] * max(0, (mid+1)*machine[j]-stock[j]) for j in range(stocknum)) > budget:\n",
    "                        break\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            ans = max(ans, mid)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        # 二分答案\n",
    "        \n",
    "        ans = 0\n",
    "        for com in composition:\n",
    "            def check(i):\n",
    "                money = 0\n",
    "                for s, base, c in zip(stock, com, cost):\n",
    "                    if s < base * i:\n",
    "                        money += (base * i - s) * c # 到达i需要购买的合金数量\n",
    "                        if money > budget:\n",
    "                            return False\n",
    "                return True\n",
    "            left, right = 0, min(stock) + budget + 1\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if check(mid):\n",
    "                    left = mid + 1 # 只用针对left操作\n",
    "                else:\n",
    "                    right = mid\n",
    "            ans = max(ans, left - 1)\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        mx = min(stock) + budget\n",
    "\n",
    "        for com in composition:\n",
    "\n",
    "            def check(num: int) -> int:\n",
    "\n",
    "                money = 0\n",
    "\n",
    "                for s, base, c in zip(stock, com, cost):\n",
    "\n",
    "                    if s < base * num:\n",
    "\n",
    "                        money += (base * num - s) * c\n",
    "\n",
    "                        if money > budget:\n",
    "\n",
    "                            return False\n",
    "\n",
    "                return True\n",
    "\n",
    "\n",
    "\n",
    "            left, right = 0, mx + 1\n",
    "\n",
    "            while left + 1 < right:  # 开区间写法\n",
    "\n",
    "                mid = (left + right) // 2\n",
    "\n",
    "                if check(mid):\n",
    "\n",
    "                    left = mid\n",
    "\n",
    "                else:\n",
    "\n",
    "                    right = mid\n",
    "\n",
    "            ans = max(ans, left)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, t: int, a: List[List[int]], b: List[int], c: List[int]) -> int:\n",
    "        ans=0\n",
    "        def check(i,m):\n",
    "            ans=0\n",
    "            for j in range(n):\n",
    "                if m*a[i][j]>b[j]:\n",
    "                    ans+=(m*a[i][j]-b[j])*c[j]\n",
    "            return ans<=t\n",
    "        for i in range(k):\n",
    "            l,r=0,t+max(b)\n",
    "            while l<r:\n",
    "                m=(l+r+1)//2\n",
    "                if check(i,m):\n",
    "                    l=m\n",
    "                else:\n",
    "                    r=m-1\n",
    "            ans=max(ans,l)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        # 确定总共制造出多少份合金，来判断是否能造出来\n",
    "        mx=min(stock)+budget\n",
    "        ans=0\n",
    "        for com in composition:\n",
    "            def check(num:int,budget:int) -> bool:\n",
    "                for s,base,c in zip(stock,com,cost):\n",
    "                    if s<base*num: # 说明为了达到能生产num个合金，必须要补充材料了\n",
    "                        budget-=(base*num-s)*c\n",
    "                        if budget<0: return False\n",
    "                return True      \n",
    "            # left=0\n",
    "            # right=mx+1 # 二分，设置一个开区间\n",
    "            # # 开区间二分的模版\n",
    "            # while left+1<right: # 始终确保区间内有一个元素\n",
    "            #     mid=(left+right)//2\n",
    "            #     if check(mid,budget):\n",
    "            #         left=mid # 只需讨论mid+1到mx之间的数，所以开区间是(mid,mx+1)\n",
    "            #     else:\n",
    "            #         right=mid\n",
    "            # ans=max(ans,left) # 最终二分终点一定是left+1=right，而这是个开区间，因此right一定不满足要求，所以满足要求的最大值一定是right-1=left\n",
    "\n",
    "            left=0\n",
    "            right=mx\n",
    "            while left<=right:\n",
    "                mid=(left+right)//2\n",
    "                if check(mid,budget):\n",
    "                    left=mid+1\n",
    "                else:\n",
    "                    right=mid-1\n",
    "            ans=max(ans,right)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, com: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        def check(m, cnt):\n",
    "            c = 0\n",
    "            for i in range(n):\n",
    "                c += max(0, cnt * com[m][i] - stock[i]) * cost[i]\n",
    "            if c <= budget:\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(k):\n",
    "            l = 0\n",
    "            r = 2 * 10**8\n",
    "            while l < r:\n",
    "                mid = (l + r + 1) >> 1\n",
    "                if check(i, mid):\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            # print(i, l)\n",
    "            res = max(res, l)\n",
    "        return res\n",
    "                        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = min(stock) + budget\n",
    "        for com in composition:\n",
    "            def check(sum: int) -> bool:\n",
    "                total = 0\n",
    "                for a, b, c in zip(com, stock, cost):\n",
    "                    if a * sum > b:\n",
    "                        total += (a * sum - b) * c\n",
    "                        if total > budget:\n",
    "                            return False\n",
    "                return True\n",
    "            l, r = 0, mx + 1 \n",
    "            while l < r:\n",
    "                mid = (l + r + 1) >> 1\n",
    "                if check(mid):\n",
    "                    l = mid \n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            ans = max(ans, r)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = min(stock) + budget\n",
    "        def check(num: int) -> int:\n",
    "            money = 0\n",
    "            for s, base, c in zip(stock, com, cost):\n",
    "                if s < base * num:\n",
    "                    money += (base * num - s) * c\n",
    "                    if money > budget:\n",
    "                        return False\n",
    "            return True\n",
    "        for com in composition:\n",
    "            left, right = 0, mx + 1\n",
    "            while left + 1 < right:  # 开区间写法\n",
    "                mid = (left + right) // 2\n",
    "                if check(mid):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "            ans = max(ans, left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(k):\n",
    "            l = min([s // c for s, c in zip(stock, composition[i])])\n",
    "            r = max([s // c for s, c in zip(stock, composition[i])]) + budget // sum(cost) + 1\n",
    "            mid=1\n",
    "            while l<r-1:\n",
    "                mid=(l+r)//2\n",
    "                b = sum([co * max(0, mid * c - s) for co, c, s in zip(cost, composition[i], stock)])\n",
    "                if b>budget:\n",
    "                    r=mid\n",
    "                else:\n",
    "                    l=mid\n",
    "            ans=max(ans,l)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        mx = 0\n",
    "        for i in range(k):\n",
    "            l ,r =0, 3*10**8\n",
    "            def check(i,mid):\n",
    "                need = 0\n",
    "                for j in range(n):\n",
    "                    need += max(0,mid*composition[i][j]-stock[j])*cost[j]\n",
    "                nonlocal budget\n",
    "                return need <= budget\n",
    "            while l < r:\n",
    "                mid = l+r+1>>1\n",
    "                if check(i,mid) : l = mid\n",
    "                else :r = mid-1\n",
    "            mx = max(mx,l)\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = min(stock) + budget\n",
    "        for com in composition:\n",
    "            def check(num: int) -> int:\n",
    "                money = 0\n",
    "                for s, base, c in zip(stock, com, cost):\n",
    "                    if s < base * num:\n",
    "                        money += (base * num - s) * c\n",
    "                        if money > budget:\n",
    "                            return  False\n",
    "                return True\n",
    "\n",
    "            left, right = 0, mx + 1\n",
    "            while left + 1 < right:\n",
    "                mid = (left + right) // 2\n",
    "                if check(mid):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "\n",
    "            ans = max(ans, left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        \n",
    "        for com in composition:\n",
    "            \n",
    "            def check(x):\n",
    "                money = 0\n",
    "                for need,base,c in zip(com,stock,cost):\n",
    "                    if x*need <= base: #初始值满足需要，不需要额外购买\n",
    "                        continue\n",
    "                    money += (x*need-base) *c \n",
    "                    if money >budget:\n",
    "                        return False\n",
    "                return True\n",
    "            \n",
    "            left ,right = 0, min(stock) + budget+1 #需要加1，防止被min(stock) + budget无法取到\n",
    "            while left<right:\n",
    "                mid = left+(right-left)//2\n",
    "                if check(mid):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "                    \n",
    "            ans = max(ans,left -1)\n",
    "        return ans\n",
    "                \n",
    "\n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "    # 最大值，二分查找\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        def total_cost(i, x):\n",
    "            s = 0\n",
    "            for a, b, c in zip(composition[i], stock, cost):\n",
    "                s += max(a * x - b, 0) * c\n",
    "\n",
    "            # print(i, x , s)\n",
    "            return s\n",
    "\n",
    "        ret = 0\n",
    "\n",
    "        for i in range(k):\n",
    "            t = bisect.bisect_right(range(int(2e8) + 1), budget, key=lambda x: total_cost(i, x))\n",
    "\n",
    "            if total_cost(i, t) > budget:\n",
    "                t -= 1\n",
    "            \n",
    "            ret = max(ret, t)\n",
    "\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "#         max_all = 0\n",
    "#         for i in range(k):\n",
    "#             s = stock.copy()\n",
    "#             money = budget; max_sin = min(s[j] // composition[i][j] for j in range(n))\n",
    "#             s = [s[j] - max_sin*composition[i][j]for j in range(n)]\n",
    "#             sum_cost = sum(composition[i][j]*cost[j]for j in range(n))\n",
    "#             while money >= 0:\n",
    "#                 if sum(s) != 0:\n",
    "#                     max_sin += 1\n",
    "#                     for j in range(n):\n",
    "#                         if s[j] >= composition[i][j]:\n",
    "#                             s[j] -= composition[i][j]\n",
    "#                         else:\n",
    "#                             money -= (composition[i][j] - s[j]) * cost[j]\n",
    "#                             s[j] = 0\n",
    "#                 else:\n",
    "#                     max_sin += money // sum_cost +1\n",
    "#                     money = -1\n",
    "#             max_all = max(max_all, max_sin - 1)\n",
    "#         return max_all\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n, k, budget, composition, stock, cost):\n",
    "        res = 0\n",
    "        for li in composition:\n",
    "            l, r = 0, 300000000  # 对应 C++ 代码中的 3e8\n",
    "            while l < r:\n",
    "                mid = (l + r + 1) // 2\n",
    "                tmp = 0\n",
    "                for i in range(n):\n",
    "                    if mid * li[i] - stock[i] > 0:\n",
    "                        tmp += (mid * li[i] - stock[i]) * cost[i]\n",
    "                if tmp <= budget:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            res = max(res, l)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "\n",
    "        def check(idx:int,x:int) ->bool:\n",
    "            nonlocal budget\n",
    "            need = composition[idx]\n",
    "            money = 0\n",
    "            for i in range(n):\n",
    "                if stock[i]>=need[i]*x:continue\n",
    "                else:\n",
    "                    money+=(need[i]*x-stock[i])*cost[i]\n",
    "            \n",
    "            return money<=budget\n",
    "\n",
    "        res = 0\n",
    "        for i in range(k):\n",
    "            l,r = 0,10**13\n",
    "            while l<r:\n",
    "                mid = l+r+1>>1\n",
    "                if check(i,mid): l = mid\n",
    "                else: r = mid-1\n",
    "            \n",
    "            res = max(res,l)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        res=0\n",
    "        mx = min(stock) + budget\n",
    "        for i in range(k):\n",
    "            def check(t):#最多合金数最少要多少预算\n",
    "                tmp=0\n",
    "                for j in range(n):\n",
    "                    if stock[j]>=t*composition[i][j]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        tmp+=(t*composition[i][j]-stock[j])*cost[j]\n",
    "                return tmp<=budget\n",
    "            l,r=0,mx\n",
    "            while l<r:\n",
    "                m=(l+r+1)//2\n",
    "                if check(m):\n",
    "                    l=m\n",
    "                else:\n",
    "                    r=m-1\n",
    "            res=max(res,l)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        for i, c in enumerate(composition):\n",
    "            l, r = 0, min((stock[i]+budget//cost[i]) // c[i] for i in range(n))\n",
    "            while l <= r:\n",
    "                m = (l+r)//2\n",
    "                if sum(max((C*(m+1)-stock[i])*cost[i], 0) for i, C in enumerate(c)) <= budget: # 能制造出m+!个合金需要的预算小于等于budget\n",
    "                    l = m+1\n",
    "                else:\n",
    "                    r = m-1\n",
    "            ans = max(ans, l)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, m: int, v: List[List[int]], s: List[int], t: List[int]) -> int:\n",
    "        ans = 0\n",
    "        l = max(s) + m\n",
    "        \n",
    "        def isok(b, i):\n",
    "            d = m\n",
    "            for j in range(n):\n",
    "                d -= max(0, b * v[i][j] - s[j]) * t[j]\n",
    "                if d < 0:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        for i in range(k):\n",
    "            a, c = 0, l\n",
    "            while a < c:\n",
    "                b = (a + c + 1) >> 1\n",
    "                if isok(b, i):\n",
    "                    a = b\n",
    "                else:\n",
    "                    c = b - 1\n",
    "            ans = max(ans, a)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 二分答案\n",
    "    # https://leetcode.cn/problems/maximum-number-of-alloys/solutions/2446024/er-fen-da-an-fu-ti-dan-by-endlesscheng-3jdr/\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = min(stock) + budget\n",
    "        for com in composition:\n",
    "            def check(num: int) -> int:\n",
    "                money = 0\n",
    "                for s, base, c in zip(stock, com, cost):\n",
    "                    if s < base * num:\n",
    "                        money += (base * num - s) * c\n",
    "                        if money > budget:\n",
    "                            return False\n",
    "\n",
    "                return True\n",
    "\n",
    "            left, right = 0, mx + 1\n",
    "            while left + 1 < right:  # 开区间写法\n",
    "                mid = (left + right) // 2\n",
    "                if check(mid):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "\n",
    "            ans = max(ans, left)\n",
    "\n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    " \n",
    "        def m(x):\n",
    "            # print(x,need)\n",
    "            mc = inf\n",
    "            for i in range(k):\n",
    "                c = 0\n",
    "                for j in range(n):\n",
    "                    need = max(composition[i][j]*x - stock[j], 0) \n",
    "                    c +=  need * cost[j]\n",
    "                # print(i, c)\n",
    "                mc = min(mc, c)\n",
    "            return mc\n",
    "        \n",
    "        ans = 0\n",
    "        left = 0 \n",
    "        right = 10**10\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2            \n",
    "            mc = m(mid)\n",
    "            if mc > budget:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "            # print (left, right)\n",
    "        return left\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        res = 0\n",
    "        for com in composition:\n",
    "            def check(target):\n",
    "                need = 0\n",
    "                for c, s, ct in zip(com, stock, cost):\n",
    "                    need += max(0, (c * target - s) * ct)\n",
    "                    if need > budget:\n",
    "                        return False \n",
    "                return True \n",
    "            l = 0\n",
    "            r = min(stock) + budget\n",
    "            while l < r:\n",
    "                mid = l + (r - l) // 2 + 1 \n",
    "                if not check(mid):\n",
    "                    r = mid - 1 \n",
    "                else:\n",
    "                    l = mid \n",
    "            res = max(res, l)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        maxcnt=0\n",
    "        def f(m):\n",
    "            l=0\n",
    "            r=budget+max(stock)\n",
    "            def valid(cnt,m):\n",
    "                s=0\n",
    "                for pos in range(len(m)):\n",
    "                    tcnt=m[pos]*cnt\n",
    "                    s+=max((tcnt-stock[pos])*cost[pos],0)\n",
    "\n",
    "                if s<=budget:\n",
    "                    return True\n",
    "                return False\n",
    "\n",
    "\n",
    "            while(True):\n",
    "                mid=(l+r)//2\n",
    "                if valid(mid,m):\n",
    "                    l=mid+1\n",
    "                else:\n",
    "                    r=mid-1\n",
    "                if l>r:\n",
    "                    break\n",
    "            return r\n",
    "\n",
    "\n",
    "        for m in composition:\n",
    "            cnt=f(m)\n",
    "            if cnt>maxcnt:\n",
    "                maxcnt=cnt\n",
    "        return maxcnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = min(stock) + budget\n",
    "        for com in composition:\n",
    "            def check(num: int) -> int:\n",
    "                money = 0\n",
    "                for s, base, c in zip(stock, com, cost):\n",
    "                    if s < base * num:\n",
    "                        money += (base * num - s) * c\n",
    "                        if money > budget:\n",
    "                            return False\n",
    "                return True\n",
    "            \n",
    "            l, r = 0, mx + 1\n",
    "            while l + 1 < r:\n",
    "                mid = (l + r) // 2\n",
    "                if check(mid):\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid\n",
    "            ans = max(ans, l)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = min(stock) + budget\n",
    "        for com in composition:\n",
    "            def check(num: int) -> int:\n",
    "                money = 0\n",
    "                for s, base, c in zip(stock, com, cost):\n",
    "                    if s < base * num:\n",
    "                        money += (base * num - s) * c\n",
    "                        if money > budget:\n",
    "                            return False\n",
    "                return True\n",
    "\n",
    "            left, right = 0, mx + 1\n",
    "            while left + 1 < right:  # 开区间写法\n",
    "                mid = (left + right) // 2\n",
    "                if check(mid):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "            ans = max(ans, left)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        \n",
    "    \n",
    "        '''\n",
    "         x.   i\n",
    "         cost = sum( (x * composition[i][j] - stock[j]) * cost[j]  for j in range(n))\n",
    "        '''\n",
    "        def ct(x:int)->int:\n",
    "            nonlocal composition,stock,cost\n",
    "            return min(sum((max(x*composition[i][j]-stock[j],0)) * cost[j] for j in range(n) ) for i in range(k))\n",
    "\n",
    "\n",
    "        l,r,ans = 0,int(1e9),0\n",
    "        while l<=r:\n",
    "            m = (l+r)//2\n",
    "            if ct(m)<=budget:\n",
    "                ans = m\n",
    "                l =m+1\n",
    "            else:\n",
    "                r = m-1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        # 二分答案\n",
    "        \n",
    "        ans = 0\n",
    "        for com in composition:\n",
    "            def check(i):\n",
    "                money = 0\n",
    "                for s, base, c in zip(stock, com, cost):\n",
    "                    if s < base * i:\n",
    "                        money += (base * i - s) * c # 到达i需要购买的合金数量\n",
    "                        if money > budget:\n",
    "                            return False\n",
    "                return True\n",
    "            left, right = 0, min(stock) + budget + 1\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if check(mid):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            ans = max(ans, left)\n",
    "        return ans - 1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        def cal(com, m): # 使用com机器 制造m合金的费用 是否不超预算\n",
    "            ans = 0\n",
    "            for i in range(n):\n",
    "                need = max(composition[com][i] * m - stock[i], 0)\n",
    "                ans += need * cost[i]\n",
    "                if ans > budget: return False\n",
    "            return True\n",
    "        ans = 0\n",
    "        mnstock = min(stock)\n",
    "        for i in range(k):\n",
    "            l, r = 0, budget + mnstock\n",
    "            while l <= r:\n",
    "                mid = l + r >> 1\n",
    "                if cal(i, mid): l = mid + 1\n",
    "                else: r = mid - 1\n",
    "            ans = max(ans, r)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        stocknum = len(stock)\n",
    "        ans = 0\n",
    "        for i, machine in enumerate(composition):\n",
    "            left = 0\n",
    "            right = 10**9+1\n",
    "            while left <= right:\n",
    "                mid = left + ((right-left)>>1)\n",
    "                sumcost = sum(cost[j] * max(0, mid*machine[j]-stock[j]) for j in range(stocknum))\n",
    "                print(left, right ,mid)\n",
    "                if sumcost <= budget:\n",
    "                    if sum(cost[j] * max(0, (mid+1)*machine[j]-stock[j]) for j in range(stocknum)) > budget:\n",
    "                        break\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            ans = max(ans, mid)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int],\n",
    "                          cost: List[int]) -> int:\n",
    "        weak_comp_indices = set()\n",
    "        for i, j in combinations(range(k), r=2):\n",
    "            if all(composition[i][t] >= composition[j][t] for t in range(n)):\n",
    "                weak_comp_indices.add(i)\n",
    "            elif all(composition[i][t] <= composition[j][t] for t in range(n)):\n",
    "                weak_comp_indices.add(j)\n",
    "        strong_comps = [composition[i] for i in range(k) if i not in weak_comp_indices]\n",
    "\n",
    "        def flag(comp, t: int) -> bool:\n",
    "            need = 0\n",
    "            for x, y, c in zip(comp, stock, cost):\n",
    "                need += max(0, t * x - y) * c\n",
    "            return need > budget\n",
    "\n",
    "        stock_value = sum(x * y for x, y in zip(stock, cost))\n",
    "\n",
    "        def bisect_t(comp) -> int:\n",
    "            unit_alloy_price = sum(x * c for x, c in zip(comp, cost))\n",
    "            lo0, hi0 = budget // unit_alloy_price, (budget + stock_value) // unit_alloy_price + 1\n",
    "            return bisect_right(range(lo0, hi0 + 1), False, key=partial(flag, comp)) - 1 + lo0\n",
    "\n",
    "        anses = list(map(bisect_t, strong_comps))\n",
    "        # print(anses)\n",
    "        return max(anses)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "\n",
    "        def check(idx:int,x:int) ->bool:\n",
    "            nonlocal budget\n",
    "            need = composition[idx]\n",
    "            money = 0\n",
    "            for i in range(n):\n",
    "                if stock[i]>=need[i]*x:continue\n",
    "                else:\n",
    "                    money+=(need[i]*x-stock[i])*cost[i]\n",
    "            \n",
    "            return money<=budget\n",
    "\n",
    "        res = 0\n",
    "        upper = max(stock) + budget \n",
    "        for i in range(k):\n",
    "            l,r = 0,upper\n",
    "            while l<r:\n",
    "                mid = l+r+1>>1\n",
    "                if check(i,mid): l = mid\n",
    "                else: r = mid-1\n",
    "            \n",
    "            res = max(res,l)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        res = 0\n",
    "        for com in composition:\n",
    "            def check(target):\n",
    "                sm = 0\n",
    "                for c, s, ct in zip(com, stock, cost):\n",
    "                    sm += max((c * target - s) * ct, 0)\n",
    "                    if sm > budget:\n",
    "                        return False \n",
    "                return True \n",
    "            l = 0\n",
    "            r = min(stock) + budget\n",
    "            while l < r:\n",
    "                mid = l + (r - l) // 2 + 1 \n",
    "                if not check(mid):\n",
    "                    r = mid - 1 \n",
    "                else:\n",
    "                    l = mid \n",
    "            res = max(res, l)\n",
    "        return res \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        def cal(com, m): # 使用com机器 制造m合金的费用 是否不超预算\n",
    "            ans = 0\n",
    "            for i in range(n):\n",
    "                need = max(composition[com][i] * m - stock[i], 0)\n",
    "                ans += need * cost[i]\n",
    "                if ans > budget: return False\n",
    "            return True\n",
    "        ans = 0\n",
    "        mnstock = min(stock)\n",
    "        for i in range(k):\n",
    "            l, r = 0, budget + mnstock # composition和cost都是1\n",
    "            while l <= r:\n",
    "                mid = l + r >> 1\n",
    "                if cal(i, mid): l = mid + 1\n",
    "                else: r = mid - 1\n",
    "            ans = max(ans, r)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        def cal(com, m): # 使用com机器 制造m合金的费用 是否不超预算\n",
    "            ans = 0\n",
    "            for i in range(n):\n",
    "                need = max(composition[com][i] * m - stock[i], 0)\n",
    "                ans += need * cost[i]\n",
    "                if ans > budget: return False\n",
    "            return True\n",
    "        ans = 0\n",
    "        mxstock = max(stock)\n",
    "        for i in range(k):\n",
    "            l, r = 0, budget + mxstock\n",
    "            while l <= r:\n",
    "                mid = l + r >> 1\n",
    "                if cal(i, mid): l = mid + 1\n",
    "                else: r = mid - 1\n",
    "            ans = max(ans, r)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "\n",
    "        def can_make(idx, num_):\n",
    "            return sum(max(0, num_*composition[idx][j]-stock[j]) * cost[j] for j in range(n)) <= budget\n",
    "\n",
    "        ub1 = 10 * max(stock[j]/cost[j] for j in range(n)) # stock\n",
    "        ub2 = max(5, 10 * max(int(budget / sum(composition[idx][j] * cost[j] for j in range(n))) for idx in range(k))) # estimated\n",
    "\n",
    "        ub = max(ub1, ub2)\n",
    "\n",
    "\n",
    "        lb = 0\n",
    "        num = 0\n",
    "        while True:\n",
    "            num = int((ub + lb) / 2)\n",
    "            can_= False\n",
    "            for i in range(k):\n",
    "                if can_make(i, num):\n",
    "                    can_ = True\n",
    "                    break\n",
    "            if can_:\n",
    "                lb = num\n",
    "            else:\n",
    "                ub = num\n",
    "            \n",
    "            if lb + 1 >= ub:\n",
    "                if not can_:\n",
    "                    num = lb\n",
    "\n",
    "                break\n",
    "\n",
    "        return num\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = min(stock) + budget\n",
    "        for com in composition:\n",
    "            def check(num: int) -> int:\n",
    "                money = 0\n",
    "                for s, base, c in zip(stock, com, cost):\n",
    "                    if s < base * num:\n",
    "                        money += (base * num - s) * c\n",
    "                        if money > budget:\n",
    "                            return False\n",
    "                return True\n",
    "\n",
    "            left, right = 0, mx + 1\n",
    "            while left + 1 < right:  # 开区间写法\n",
    "                mid = (left + right) // 2\n",
    "                if check(mid):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "            ans = max(ans, left)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        def check(num: int) -> bool:\n",
    "            money = 0\n",
    "            for s, base, c in zip(stock, com, cost):\n",
    "                if s < base * num:\n",
    "                    money += (base * num - s) * c\n",
    "                    if money > budget:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        ans = 0\n",
    "        mx = min(stock) + budget\n",
    "        for com in composition:\n",
    "            l, r = 0, mx\n",
    "            while l < r:\n",
    "                mid = l + r + 1 >> 1\n",
    "                if check(mid): l = mid\n",
    "                else: r = mid - 1\n",
    "            ans = max(ans, r)\n",
    "        return ans\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        ans=0\n",
    "        mx=min(stock)+budget\n",
    "        for com in composition:\n",
    "            def ff(num):\n",
    "                money=0\n",
    "                for s,cm,c in zip(stock,com,cost):\n",
    "                    if s<cm*num:\n",
    "                        money+=(cm*num-s)*c\n",
    "                        if money>budget:\n",
    "                            return False\n",
    "                return True   \n",
    "            left,right=0,mx+1\n",
    "            while left+1<right:\n",
    "                mid=(left+right)//2\n",
    "                if ff(mid):\n",
    "                    left=mid \n",
    "                else:\n",
    "                    right=mid \n",
    "            ans=max(ans,left)          \n",
    "        return ans           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:    \n",
    "        ans = 0\n",
    "        mx = min(stock) + budget\n",
    "        for com in composition:\n",
    "            def check(num):\n",
    "                money = 0\n",
    "                for s, base, c in zip(stock, com, cost):\n",
    "                    if s < base * num:\n",
    "                        money += (base * num - s) * c\n",
    "                        if money > budget:\n",
    "                            return False\n",
    "                return True\n",
    "\n",
    "            left = 0\n",
    "            right = mx + 1\n",
    "            while left+1 < right:\n",
    "                mid = (left + right) // 2\n",
    "                if check(mid):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "\n",
    "            ans = max(ans, left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "    R = min(stock) + budget\n",
    "    res = 0\n",
    "    for com in composition:\n",
    "      l, r = 0, R\n",
    "      def check(mid):\n",
    "        t = budget\n",
    "        for i in range(len(com)):\n",
    "          buy = mid * com[i] - stock[i]\n",
    "          if buy > 0:\n",
    "            if(buy > t / cost[i]): return False\n",
    "            t -= buy * cost[i]\n",
    "        return t >= 0\n",
    "      while l < r:\n",
    "        mid = (l + r + 1) // 2\n",
    "        if check(mid):\n",
    "          l = mid\n",
    "        else:\n",
    "          r = mid - 1\n",
    "      res = max(res, l)\n",
    "    return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        def check(v):\n",
    "            for i in range(k):\n",
    "                ans = 0\n",
    "                for j in range(n):\n",
    "                    ans += max(v * composition[i][j] - stock[j], 0) * cost[j]\n",
    "                if ans <= budget:\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        l = 0\n",
    "        r = 10 ** 9\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return r\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        def check(d, com):\n",
    "            cur_cost = 0\n",
    "            for i in range(n):\n",
    "                if stock[i] < com[i] * d:\n",
    "                    cur_cost += (com[i] * d - stock[i]) * cost[i]\n",
    "                    if cur_cost > budget:\n",
    "                        return False\n",
    "            return True\n",
    "        res = 0\n",
    "        for com in composition:\n",
    "            l = -1\n",
    "            r = 2 * 10 ** 8 + 1\n",
    "            while l + 1 != r:\n",
    "                mid = l + (r - l) // 2\n",
    "                if check(mid, com):\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid\n",
    "            res = max(res, l)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "stock[i]：第i种金属的数量\n",
    "composition[i][j]：对于第i台机器来说，需要[i][j]个j类型的金属\n",
    "n：总共有n种金属\n",
    "k：总共有k台机器\n",
    "那么其实就是对于每一个机器的情况单独做处理，会得到一个列表，这个列表中最大的数的index+1就是答案\n",
    "\n",
    "因此首先要对每台机器进行单独处理\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        res = 0\n",
    "        for com in composition:\n",
    "            def check(target):\n",
    "                need = 0\n",
    "                for c, s, ct in zip(com, stock, cost):\n",
    "                    need += max(0, (target * c - s) * ct)\n",
    "                    if need > budget:\n",
    "                        return False \n",
    "                return True \n",
    "            l = 0\n",
    "            r = min(stock) + budget\n",
    "            while l < r:\n",
    "                mid = l + (r - l) // 2 + 1 \n",
    "                if not check(mid):\n",
    "                    r = mid - 1 \n",
    "                else:\n",
    "                    l = mid \n",
    "            res = max(res, l)\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        \"\"\" Binary Search \"\"\"\n",
    "\n",
    "        ans = 0 \n",
    "        upper = max(stock) + budget \n",
    "\n",
    "        for quant in composition:\n",
    "            def check(num):\n",
    "                est = 0\n",
    "                for s, c, q in zip(stock, cost, quant):\n",
    "                    if s < q * num:\n",
    "                        est += (q * num - s) * c \n",
    "                        if est > budget:\n",
    "                            return False \n",
    "                return True  \n",
    "\n",
    "            left, right = 0, upper\n",
    "            while left < right:\n",
    "                mid = (right - left + 1) // 2 + left \n",
    "                if check(mid):\n",
    "                    left = mid  \n",
    "                else:\n",
    "                    right = mid - 1 \n",
    "                    \n",
    "            ans = max(ans, right)  \n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        def check(num):\n",
    "            money = 0\n",
    "            for s, base, c in zip(stock, com, cost):\n",
    "                if s < num * base:\n",
    "                    money += (num * base - s)*c \n",
    "                    if money > budget:\n",
    "                        return False\n",
    "            return True\n",
    "        result = 0\n",
    "        mx = min(stock) + budget\n",
    "        for com in composition:\n",
    "            left, right = 0, mx + 1\n",
    "            while left + 1 < right:\n",
    "                mid = (left + right)//2\n",
    "                if check(mid):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "            result = max(result, left)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = int(2e8)\n",
    "        for com in composition:\n",
    "            def check(num: int) -> bool:\n",
    "                money = 0\n",
    "                for s, base, c in zip(stock, com, cost):\n",
    "                    if s < base * num:\n",
    "                        money += (base * num - s) * c\n",
    "                        if money > budget: return False\n",
    "                return True\n",
    "            left, right = 0, mx + 1\n",
    "            while left + 1 < right:\n",
    "                mid = (left + right) // 2\n",
    "                if check(mid):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "            ans = max(ans, left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        res = 0\n",
    "        for com in composition:\n",
    "            def check(target):\n",
    "                need = 0\n",
    "                for c, s, ct in zip(com, stock, cost):\n",
    "                    need += max(0, (target * c - s) * ct)\n",
    "                    if need > budget:\n",
    "                        return False \n",
    "                return True \n",
    "\n",
    "            l = 0\n",
    "            r = min(stock) + budget\n",
    "            while l < r:\n",
    "                mid = l + (r - l) // 2 + 1\n",
    "                if not check(mid):\n",
    "                    r = mid - 1 \n",
    "                else:\n",
    "                    l = mid \n",
    "            res = max(res, l)\n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "     res = 0\n",
    "     mx = min(stock) + budget\n",
    "     for com in composition:\n",
    "         def check(num):\n",
    "             m = 0\n",
    "             for s,base,c in zip(stock,com,cost):\n",
    "                 if s< base *num:\n",
    "                     m += (base*num-s)*c\n",
    "                     if m> budget:\n",
    "                         return False\n",
    "             return True\n",
    "\n",
    "         l = 0\n",
    "         r = mx + 1\n",
    "         while l +1 < r:\n",
    "             mid = (l+r)//2\n",
    "             if check(mid):\n",
    "                 l = mid\n",
    "             else:\n",
    "                 r = mid\n",
    "         res = max(res,l)\n",
    "     return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        res = 0\n",
    "        for com in composition:\n",
    "            def check(target):\n",
    "                need = 0\n",
    "                for c, s, ct in zip(com, stock, cost):\n",
    "                    need += max(0, (target * c - s) * ct)\n",
    "                    if need > budget:\n",
    "                        return False \n",
    "                return True \n",
    "            l = 0\n",
    "            r = min(stock) + budget\n",
    "            while l < r:\n",
    "                mid = l + (r - l) // 2 + 1 \n",
    "                if not check(mid):\n",
    "                    r = mid - 1 \n",
    "                else:\n",
    "                    l = mid \n",
    "            res = max(res, l)\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        def judge(x: int, ww):\n",
    "            t_cost = 0\n",
    "            for j in range(n):\n",
    "                cnt = ww[j] * x\n",
    "                if cnt <= stock[j]:\n",
    "                    pass\n",
    "                else:\n",
    "                    t_cost += (cnt-stock[j]) * cost[j]\n",
    "                # print(\"judge\",x, j, cnt-stock[j], t_cost)\n",
    "            if t_cost <= budget:\n",
    "                return True\n",
    "            return False \n",
    "\n",
    "        ret = 0\n",
    "        for i in range(k):\n",
    "            w = composition[i]\n",
    "            left = 0\n",
    "            right = int(1e9) \n",
    "            while left <= right:\n",
    "                mid = (left+right)//2\n",
    "                # print(left, right, mid)\n",
    "                if judge(mid, w):\n",
    "                    left = mid + 1 \n",
    "                else:\n",
    "                    right = mid - 1 \n",
    "            # print(\"left\", left, right)\n",
    "            ret = max(ret, left-1)\n",
    "        return ret         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:\n",
    "        # composition = [\n",
    "        #                [1,1,1],\n",
    "        #                [1,1,10]\n",
    "        #               ]\n",
    "        # stock = [0,0,0]\n",
    "        # cost = [1,2,3]\n",
    "        # n合金类型\n",
    "        # K机器数 100台\n",
    "        ans = 0\n",
    "        mx = min(stock) + budget\n",
    "        # O(k)\n",
    "        for com in composition:\n",
    "            def check(num):\n",
    "                money = 0\n",
    "                for s,base,c in zip(stock,com,cost):\n",
    "                    if s < base*num:\n",
    "                        money += (base * num - s) * c\n",
    "                        if money > budget:\n",
    "                            return False\n",
    "                return True\n",
    "            left,right = 0,mx + 1\n",
    "            while left + 1 < right:\n",
    "                mid = (left + right)//2\n",
    "                if check(mid):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "            ans = max(ans,left)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
